/*
	author: TangQiao , Wind @ Beijing Normal University

	problem name: Highways
	
	source :  PKU Online Judge
	
	problem type: 图论 最小生成树

	
	problem solution: prim算法 或 floyd算法
	
		
	faults:本来是输出最小树的最大值,我误认为是求最大树的最小值.
	
	date : 2005.7.13 北大个人练习赛
	
*/
#include <stdio.h>

int dis[505][505];
int n;

main()
{
//	freopen("input","r",stdin);
	int icase;
	int i,j,k;
	int max;

	scanf("%d", &icase);
	while (icase-->0)
	{
		scanf("%d", &n);

		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				scanf("%d", &dis[i][j]);

		for (k=1;k<=n;k++)
			for (i=1;i<n;i++)
				if (k!=i)
					for (j=i+1;j<=n;j++)
						if (i!=j && j!=k)
							if ((max=dis[i][k]>dis[k][j]?dis[i][k]:dis[k][j])<dis[i][j])
								dis[i][j]=dis[j][i]=max;

		max=0;
		for (i=1;i<n;i++)
			for (j=i+1;j<=n;j++)
				if (max<dis[i][j])
					max=dis[i][j];

		printf("%d\n", max);

	}

	return 0;
}